Search for: All records

Abstract We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$ ${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ ${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$ $Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$ $A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$ $b\in Z^m$and$$\varvec{x}$$ $x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$ ${\ell }_0$-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$ $R$, to other subdomains such as$$\mathbb {Z}$$ $Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.